class Solution {
    /**
     * 思路: 单调栈
     *  我们可以把数组看作3份,lis1+lis2+lis3
     *  如[1,3,5][8,2]:
     *                 lis1 和 lis2的部分元素单调递增,那么如何找到left使得区分lis1和lis2呢?
     *                 假设lis2+lis3中最小元素为minx,那么lis1中所有元素都会小于minx
     */
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;

        int left = len - 1;
        Deque<Integer> st = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            // 出栈元素都会截断单调递增的lis1
            while (st.size() > 0 && nums[i] < nums[st.getLast()]) {
                left = Math.min(left, st.removeLast());
            }
            st.addLast(i);
        }
        if (left == len - 1)
            return 0;

        //System.out.println(st);
        int right = 0;
        st.clear();
        for (int i = len - 1; i >= 0; i--) {
            while (st.size() > 0 && nums[i] > nums[st.getLast()]) {
                right = Math.max(right, st.removeLast());
            }
            st.addLast(i);
        }
        //System.out.println(st);
        // System.out.println("left="+left+",right="+right);


        return right - left + 1;
    }
}